import java.util.Arrays;

public class TestDemo {
//    三个数的最大乘积
//    整形数组nums 在数组中找出三个数字组成的最大乘积 并输出
    public static void main(String[] args) {
        System.out.println(getMax(new int[]{-5,-1,-6,2,3,4,5}));//150
        System.out.println(getMax2(new int[]{-5,-1,-6,2,3,4,5}));//150
    }

//    排序  时间复杂度NlogN  就是Arrays排序的时间复杂度
    public static int getMax(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        return Math.max(nums[0]*nums[1]*nums[length-1], nums[length-1]*nums[length-2]*nums[length-3]);
    }



//    线性扫描
    public static int getMax2(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            }else if (x < min2) {
                min2 = x;
            }

            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }else if (x > max2) {
                max3 = max2;
                max2 = x;
            }else if (x > max3) {
                max3 = x;
            }
        }
        return Math.max(min1*min2*max1, max1*max2*max3);
    }
}
